package mianshi;

/**
 * description:
 * author:张腾
 * date:2021-07-18
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
 * 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek返回 -1。
 */
public class _03_05 {
    class SortedStack {
        private Deque<Integer> stack1;
        private Deque<Integer> stack2;
        public SortedStack() {
            stack1 = new ArrayDeque<>();
            stack2 = new ArrayDeque<>();
        }

        public void push(int val) {
            while (!stack1.isEmpty()){
                if (stack1.peek()<val) {
                    stack2.push(stack1.pop());
                }else{
                    stack1.push(val);
                    break;
                }
            }
            if (stack1.isEmpty()) stack1.push(val);
            while (!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
        }

        public void pop() {
            if (!stack1.isEmpty())
                stack1.pop();
        }

        public int peek() {
            return stack1.isEmpty()?-1:stack1.peek();
        }

        public boolean isEmpty() {
            return stack1.isEmpty();
        }
    }
}
